/**
 * @file 005.单词长度的最大乘积.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-06
 *
 * @copyright Copyright (c) 2021
 *
 * 位运算模拟
 * 朴素的做法是：遍历words每一对单词，判断这对单词是否有公共字母
 * 位运算加速是把判断是否含公共字母加速到了O(1)
 * 提前打表好mask[i]，做“或运算”
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    int maxProduct(vector<string> &words)
    {
        int n = words.size();
        vector<int> mask(n, 0); // int有32位，做26位绰绰有余
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < words[i].size(); ++j) {
                mask[i] |= 1 << (words[i][j] - 'a');
            }
        }
        int maxMulti = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (!(mask[i] & mask[j])) { // 无公共字母
                    maxMulti = max(maxMulti, int(words[i].size() * words[j].size()));
                }
            }
        }
        return maxMulti;
    }
};

int main()
{
    vector<string> words1 = {"abcw", "baz", "foo", "bar", "fxyz", "abcdef"};
    vector<string> words2 = {"a", "ab", "abc", "d", "cd", "bcd", "abcd"};
    vector<string> words3 = {"a", "aa", "aaa", "aaaa"};
    cout << Solution().maxProduct(words1) << endl;
    cout << Solution().maxProduct(words2) << endl;
    cout << Solution().maxProduct(words3) << endl;
    return 0;
}